//include/deal.II-translator/A-headers/reordering_0.txt
// ---------------------------------------------------------------------
//
// Copyright (C) 2002 - 2021 by the deal.II authors
//
// This file is part of the deal.II library.
//
// The deal.II library is free software; you can use it, redistribute
// it, and/or modify it under the terms of the GNU Lesser General
// Public License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
// The full text of the license can be found in the file LICENSE.md at
// the top level directory of deal.II.
//
// ---------------------------------------------------------------------

/**
 *    @defgroup reordering Grid reordering and cell orientation
 *
 * @brief A module describing how deal.II consistently orients Triangulation
 * 对象。 <h3>Statement of problems</h3>
 * 在deal.II中的三角形有一个特殊的结构，即不仅有单元，而且有面，在三维中还有边，它们都是自己的对象。面和边都有独特的方向，而且它们相对于相邻的单元也有特定的方向。因此，在两个空间维度中分隔两个单元的线不仅有一个方向，而且相对于与第一条线相邻的两个四边形的其他线，它也必须有一个明确的方向。同样的定义也适用于三维单元和分隔它们的物体（线、四边形）。
 * 例如，在二维空间中，一个四边形由四条线组成，这些线有一个方向，根据定义是这样的。
 * @verbatim
 * 2-->--3
 * |     |
 * ^     ^
 * |     |
 * 0-->--1
 * @endverbatim
 * 现在，两个相邻的单元格必须有一个顶点编号，使公边的方向相同。例如，以下两个四边形
 * @verbatim
 * 3---4---5
 * |   |   |
 * 0---1---2
 * @endverbatim
 * 可以用顶点编号<tt>(0 1 3 4)</tt>和<tt>(1 2 4
 * 5)</tt>来描述，因为从两个单元格看，中间线会得到方向<tt>1->4</tt>。
 * 编号<tt>(0 1 3 4)</tt>和<tt>(5 4 2
 * 1)</tt>将是不允许的，因为左边的四边形会给公共线以<tt>1->4</tt>的方向，而右边的会想用<tt>4->1</tt>，导致歧义的产生。
 * 作为附带说明，我们注意到，如果人们采纳了拥有面的方向是有用的这一观点，那么如上所示的一个单元的四个面的方向几乎是必要的。特别是，不可能使它们的方向代表（逆）时针的意义，因为那样的话，我们就不能为下面的三块细胞找到一个有效的方向。
 * @verbatim
 *     o
 *   /   \
 * o       o
 * | \   / |
 * |   o   |
 * |   |   |
 * o---o---o
 * @endverbatim
 * （读者需要尝试找到一个符合要求的线方向的选择；很快就会发现不可能存在这样的东西，即使我们允许可能存在同时具有顺时针和逆时针方向的线的单元。
 * 有人可能会说，对面和边的唯一方向的定义，以及相对于它们所约束的单元格的方向的定义，是deal.II的一个错误特征。事实上，这使得阅读由网格生成器创建的网格变得相当困难，因为它们在生成输出时通常不会遵循这些惯例。另一方面，有很好的理由引入这些约定，因为它们在很多情况下可以使编程变得更简单，导致一些计算速度的提高，因为我们可以在很多地方避免昂贵的检查，因为面的方向是已知的，假设它是由三角法保证的。
 * 本课的目的是为一组给定的单元格找到一个排序，使生成的三角形满足上述的所有要求。为此，我们将首先展示一些例子，说明为什么这是一个困难的问题，然后开发找到这种重新排序的算法。请注意，该算法是在一组CellData对象上操作的，这些对象是用来向三角剖分类描述一个网格的。例如，这些对象是由GridIn类在从输入文件读入网格时生成的。
 * 作为第一节的最后一个问题：对于一个给定的领域细分为单元格，是否能保证面的这种方向总是存在？下面描述的2d的线性复杂度算法也证明了2d的答案是肯定的。对于3D，答案是否定的（这也强调了使用这种方向可能是一种
 *
 * --不幸的是无法治愈的
 *
 * - 交易二的错误特征）。)一个简单的三维反例说明了这一点：取一串三维单元并将其弯曲成一个环形。由于单元中的对立线需要有相同的方向，所以对它们有一个简单的排序，例如所有的线都是径向向外，切向顺时针，和轴向向上的。然而，如果在连接细胞串的两端之前，将细胞串扭转180度，那么就不可能再有这样的方向，这一点可以很容易地检查出来。实际上，有些网格不能用于deal.II。为了克服这个问题，引入了 <code>face_rotation</code> 、 <code>face_flip</code> and <code>line_orientation</code> 标志。有了这些标志，就有可能处理所有的纯六面体网格。然而，为了减少可能的bug的影响，还是应该尝试对网格进行重新排序。只有当这个程序失败时，才应该使用原始的连接信息。
 *
 *  <h3>Examples of problems</h3>
 * 如前所述，对单元格的顶点列表进行重新排序，从而得到的网格并不是一个微不足道的问题。特别是，只看一个单元格的邻域往往是不够的，它不能在不违反上述要求的情况下被添加到其他单元格的集合中。我们将展示两个例子，这一点很明显。
 * 第一个这样的例子是下面的，我们将称之为
 * "最后的四个单元格"，因为这四个单元格靠近每一行三个垂直单元格的右端（在下面的图片中，我们只显示了左边的这样一列三个单元格，但是我们将指出如果我们延长这个列表会发生什么）。
 * @verbatim
 * 9---10-----11
 * |   |    / |
 * 6---7---8  |
 * |   |   |  |
 * 3---4---5  |
 * |   |    \ |
 * 0---1------2
 * @endverbatim
 * 假设你在左侧边界的单元格中对顶点进行了编号，从而诱导出以下线条方向。
 * @verbatim
 * 9->-10-----11
 * ^   ^    / |
 * 6->-7---8  |
 * ^   ^   |  |
 * 3->-4---5  |
 * ^   ^    \ |
 * 0->-1------2
 * @endverbatim
 * 例如，这可以通过使用索引<tt>（0 1 3 4）</tt>，<tt>（3 4 6
 * 7）</tt>，<tt>（6 7 9
 * 10）</tt>来完成。现在，你将找不到一种方法来给出正确的单元格的指数，而又不对某条线或其他线引入歧义，或者不违反每个单元格内必须有一个顶点，两条线都从这个顶点出发，而相邻的两条线都指向这个顶点。
 * 在这种情况下，解决方案是对三个左边单元格中的一个重新编号，例如，通过对左上角单元格的编号<tt>(9
 * 6 10 7)</tt>来恢复顶点7和10之间的线的意义。
 * @verbatim
 * 9->-10-----11
 * v   v    / |
 * 6->-7---8  |
 * ^   ^   |  |
 * 3->-4---5  |
 * ^   ^    \ |
 * 0->-1------2
 * @endverbatim
 *
 * 这里的重点是：假设我们想把网格向左延长，像这样。
 * @verbatim
 * o---o---o---o---o------o
 * |   |   |   |   |    / |
 * o---o---o---o---o---o  |
 * |   |   |   |   |   |  |
 * o---o---o---o---o---o  |
 * |   |   |   |   |    \ |
 * o---o---o---o---o------o
 * @endverbatim
 * 然后我们会遇到和上面一样的问题，如果我们把左边的单元格统一排序，从而迫使我们把一个单元格（就是上面我们可以排序为<tt>(9
 * 6 7
 * 10)</tt>的那个单元格）的排序还原。然而，由于相反的线必须有相同的方向，这又会迫使我们旋转它左边的单元格，然后再旋转左边的单元格，如此反复，直到我们到达网格的左端。因此，这是一个我们必须追溯到第一列的三个单元的例子，以找到一个一致的排序，如果我们最初是均匀地排序。
 * 作为第二个例子，请考虑下面这个简单的网格，其中单元格的编号顺序很重要。
 * @verbatim
 * 3-----2-----o-----o ... o-----7-----6
 * |     |     |     |     |     |     |
 * |  0  |  N  | N-1 | ... |  2  |  1  |
 * |     |     |     |     |     |     |
 * 0-----1-----o-----o ... o-----4-----5
 * @endverbatim
 * 我们在这里只指出了相关顶点的数字。假设用户通过顶点指数<tt>0
 * 1 3 2</tt>和<tt>6 7 5
 * 4</tt>给单元格0和1。那么，如果我们按照这个方向，为这两个单元格创建线条后的网格会是这样的。
 * @verbatim
 * 3-->--2-----o-----o ... o-----7--<--6
 * |     |     |     |     |     |     |
 * ^  0  ^  N  | N-1 | ... |  2  v  1  v
 * |     |     |     |     |     |     |
 * 0-->--1-----o-----o ... o-----4--<--5
 * @endverbatim
 * 现在，由于相反的线必须指向同一方向，我们只能将单元格2到N-1添加到单元格1，使所有垂直线都指向下方。然而，我们不能向任何方向添加单元格N，因为它将有两条不指向同一方向的相反线。我们必须旋转0号或1号单元格，以便能够添加所有其他单元格，从而满足交易.II三角形的要求。
 * 这两个例子说明，如果我们在某个方向上添加了一定数量的单元格，而在添加下一个单元格时又不能不引入已经在另一个方向上添加的面，那么只旋转我们未能添加的单元格附近的单元格可能是不够的。可能有必要回到很远的地方，旋转很久以前就已经输入的单元。
 *
 *  <h3>Solution</h3>
 * 从上面的例子可以看出，如果我们遇到一个不能被添加到已经输入的单元格中的单元格，我们通常不能指出哪个单元格是罪魁祸首，必须以不同的方向输入。此外，即使我们知道哪个单元格，也可能有大量的单元格不再适合于网格，我们也必须找到不同的方向（在上面的第二个例子中，如果我们旋转了单元格1，那么我们也必须旋转单元格1到N-1）。
 * 解决这个问题的蛮力方法如下：如果单元格N不能被添加，那么就尝试旋转单元格N-1。如果我们不能再旋转单元格N-1，那么就尝试旋转单元格N-2，并尝试用单元格N-1的所有方向添加单元格N。以此类推。在算法上，我们可以用一个树状结构来表示，节点N有多少个子节点N+1的可能方向，就有多少个子节点（在两个空间维度上，有四个方向，每个单元可以由其四个顶点构建。例如，如果顶点指数是<tt>(0
 * 1 3 2)</tt>，那么四个可能性是<tt>(0 1 3 2)</tt>，<tt>(1 3 2
 * 0)</tt>，<tt>(3 2 0 1)</tt>，和<tt>(2 0 1
 * 3)</tt>）。)当添加一个又一个单元格时，我们以深度优先（pre-order）的方式遍历这个树。当我们遇到从根（单元格0）到叶（最后一个单元格）的路径不允许时（也就是说，通过树的路径所编码的单元格的方向不能导致有效的三角形），我们必须追踪并尝试通过树的另一条路径。
 * 当然，在实践中，我们并不是沿着每条路径走到最后一个节点，然后找出一条路径是否导致了有效的三角结构，而是使用一个归纳论证：如果对于所有先前添加的单元格，三角结构是有效的，那么我们可以通过检查进入当前单元格是否会引入任何具有非唯一方向的面，来找出一条穿过树的路径是否可以产生有效的三角结构；如果是这样，那么我们可以停止跟踪这一点以下的所有路径并立即追踪回去。
 * 尽管如此，已经很明显的是，这棵树在两个空间维度上有
 * $4^N$ 个叶子，因为每个 $N$
 * 个单元可以在四个方向上添加。这些节点中的大部分可以被迅速丢弃，因为首先第一个单元格的方向是不相关的，其次如果我们添加的一个单元格的邻居已经被添加了，那么已经只剩下两个可能的方向了，所以我们要做的检查总数直到我们找到一个有效的方式，明显小于
 * $4^N$
 * 。然而，该算法在时间上仍然是指数级的，在内存上是线性的（我们只需要以已经添加的单元格的方向堆栈的形式来存储当前路径的信息）。
 * 事实上，上面的两个例子表明，指数估计并不是悲观的：我们确实要追踪到那里的一个最开始的单元格，以找到一个以一致方式添加所有单元格的方法。
 * 这种令人沮丧的情况因以下事实而大为改善：我们有一种用于2D的替代算法，在运行时间上总是线性的（由德克萨斯大学TICAM的迈克尔-安德森在2003年发现并实现），而对于3D，我们可以找到一种算法，在实践中通常只在时间和内存上是大致线性的。我们将在下文中描述这些算法。完整的描述和理论分析见
 * @cite AABB17  。
 *
 *  <h3>The 2d linear complexity algorithm</h3>
 * 该算法使用了这样一个事实：一个单元格的相对面需要有相同的方向。所以你从一条任意的线开始，选择一个方向。那么对面的面的方向就已经固定了。然后去看我们已经固定的两个面对面的两个单元格：对它们来说，一个面已经固定了，所以我们也可以固定对面的面。继续这样做。最终，我们对一连串的单元格进行了这样的处理。然后从一个已经有两个固定面的单元格中抽取一个非固定面，再做一遍。
 * 更详细地说，这个算法最好用一个例子来说明。我们考虑下面的网格。
 * @verbatim
 * 9------10-------11
 * |      |        /|
 * |      |       / |
 * |      |      /  |
 * 6------7-----8   |
 * |      |     |   |
 * |      |     |   |
 * |      |     |   |
 * 3------4-----5   |
 * |      |      \  |
 * |      |       \ |
 * |      |        \|
 * 0------1---------2
 * @endverbatim
 * 首先选择一个单元格（本例中为（0,1,3,4））。单元的一个侧面被任意地定向（3->4）。这个方向的选择然后在网格中传播，跨越边和元素。(0->1),
 * (6->7)和(9->10)。这涉及到边跳和面跳，给出了一个以圆点显示的穿过网格的路径。
 * @verbatim
 * 9-->--10-------11
 * |  .  |        /|
 * |  .  |       / |
 * |  .  |      /  |
 * 6-->--7-----8   |
 * |  .  |     |   |
 * |  .  |     |   |
 * |  .  |     |   |
 * 3-->--4-----5   |
 * |  .  |      \  |
 * |  X  |       \ |
 * |  .  |        \|
 * 0-->--1---------2
 * @endverbatim
 * 然后对所选元素的其他面重复这一过程，对网格的更多面进行定向。
 * @verbatim
 * 9-->--10-------11
 * |     |        /|
 * v.....v.......V |
 * |     |      /. |
 * 6-->--7-----8 . |
 * |     |     | . |
 * |     |     | . |
 * |     |     | . |
 * 3-->--4-----5 . |
 * |     |      \. |
 * ^..X..^.......^ |
 * |     |        \|
 * 0-->--1---------2
 * @endverbatim
 * 一旦一个元素被完全定向，就不需要再考虑了。这些元素在图中用o来填充。然后我们转到下一个元素。
 * @verbatim
 * 9-->--10->-----11
 * | ooo |  .     /|
 * v ooo v  .    V |
 * | ooo |  .   /  |
 * 6-->--7-->--8   |
 * |     |  .  |   |
 * |     |  .  |   |
 * |     |  .  |   |
 * 3-->--4-->--5   |
 * | ooo |  .   \  |
 * ^ ooo ^  X    ^ |
 * | ooo |  .     \|
 * 0-->--1-->------2
 * @endverbatim
 * 重复这样做可以得到
 * @verbatim
 * 9-->--10->-----11
 * | ooo | oooooo /|
 * v ooo v ooooo V |
 * | ooo | oooo /  |
 * 6-->--7-->--8   |
 * |     |     |   |
 * ^.....^..X..^...^
 * |     |     |   |
 * 3-->--4-->--5   |
 * | ooo | oooo \  |
 * ^ ooo ^ ooooo ^ |
 * | ooo | oooooo \|
 * 0-->--1-->------2
 * @endverbatim
 * 而最终的导向网是
 * @verbatim
 * 9-->--10->-----11
 * |     |        /|
 * v     v       V |
 * |     |      /  |
 * 6-->--7-->--8   |
 * |     |     |   |
 * ^     ^     ^   ^
 * |     |     |   |
 * 3-->--4-->--5   |
 * |     |      \  |
 * ^     ^       ^ |
 * |     |        \|
 * 0-->--1-->-------2
 * @endverbatim
 * 很明显，这个算法的运行时间是线性的，因为它对每个面只精确地接触一次。
 * 刚才在二维情况下描述的算法在这个类中对二维和（通用形式）三维都有实现。三维情况下，使用片状而不是单元格串来工作。如果网格是可定向的，那么该算法能够在线性时间内完成其工作；如果它是不可定向的，那么它也会在线性时间内中止。
 * 这两种算法在论文 "On orienting edges of unstructured two- and
 * three-dimensional meshes "中描述，R. Agelek, M. Anderson, W. Bangerth,
 * W. L. Barth, ACM Transactions on Mathematical Software, vol. 44, article 5,
 * 2017。预印本可作为<a href="http://arxiv.org/abs/1512.02137">arxiv
 * 1512.02137</a>使用。
 *
 *  <h3>For the curious</h3> 在实现上述算法之前（最初由Michael
 * Anderson在2002年实现，由Wolfgang Bangerth在2016年根据 @cite
 * AABB17 中的工作重新实现），我们使用了一个最初由Wolfgang
 * Bangerth在2000年实现的分支和切割算法。虽然它不再被使用，但这里是它的工作原理，以及为什么它不总是对大网格有效，因为它的运行时间在糟糕的情况下可能是指数级的。
 * 第一个观察结果是，虽然有反例，但问题通常是局部的。例如，在上面提到的第二个例子中，如果我们对单元格进行了编号，使相邻的单元格具有相似的单元格号，那么需要的回溯量就会大大减少。因此，在算法的实施过程中，第一步是以Cuthill-McKee的方式对单元格进行重新编号：从邻居数量最少的单元格开始，给它分配单元格编号为0。然后找到这个单元格的所有邻居，再给它们分配连续的数字。然后找到它们尚未被编号的邻居，给它们编号，以此类推。从图形上看，这意味着找到连续远离初始单元的单元区，并以这种前行的方式为它们编号。这已经大大改善了问题的局部性，从而减少了必要的回溯量。
 * 第二点是，我们可以使用一些方法来修剪树，这通常会导致所有单元的有效方向非常快。
 * 第一个方法是基于这样的观察：如果我们不能插入一个编号为N的单元格，那么这可能不是由于单元格N-1造成的，除非N-1是N的直接邻居。原因很明显：单元格M的选择方向只能影响添加单元格N的可能性，如果它是一个直接邻居，或者如果有一连串的单元格在M之后被添加并且连接单元格M和N。反过来说，如果我们不能添加单元格N，那么就没有必要追踪到单元格N-1，但我们可以追踪到单元格索引最大且已经被添加的N的邻居。
 * 不幸的是，如果不谨慎应用，这种方法可能无法产生一个有效的树的路径。考虑以下情况，最初是从BAMG程序自动生成的950个单元的网格中提取的（这个程序通常生成的网格是相当不平衡的，通常有许多
 *
 * - 有时是10个或更多
 *
 * - 一个顶点的邻居，并且在最初的算法中暴露了一些问题；还要注意的是，这个例子是在2D中，我们现在有上面描述的更好的算法，但同样的观察也适用于3D）。)
 * @verbatim
 * 13----------14----15
 * | \         |     |
 * |  \    4   |  5  |
 * |   \       |     |
 * |    12-----10----11
 * |     |     |     |
 * |     |     |  7  |
 * |     |     |     |
 * |  3  |     8-----9
 * |     |     |     |
 * |     |     |  6  |
 * |     |     |     |
 * 4-----5-----6-----7
 * |     |     |     |
 * |  2  |  1  |  0  |
 * |     |     |     |
 * 0-----1-----2-----3
 * @endverbatim
 * 请注意，中间有一个洞。现在假设用户用顶点数字<tt>2 3 6
 * 7</tt>来描述第一个单元格0，用<tt>15 14 11
 * 10</tt>来描述单元格5，并假设单元格1、2、3、4的编号是可以在初始旋转中加入5。所有其他的单元格都以通常的方式进行编号，即从左下角开始，逆时针计数。鉴于对单元格的这种描述，算法将从零单元格开始，一个接一个地添加单元格，直到第六个。然后情况会是这样的。
 * @verbatim
 * 13----->---14--<--15
 * | \         |     |
 * |  >    4   v  5  v
 * |   \       |     |
 * |    12->--10--<--11
 * |     |     |     |
 * ^     |     |  7  |
 * |     |     |     |
 * |  3  ^     8-->--9
 * |     |     |     |
 * |     |     ^  6  ^
 * |     |     |     |
 * 4-->--5-->--6-->--7
 * |     |     |     |
 * ^  2  ^  1  ^  0  ^
 * |     |     |     |
 * 0-->--1-->--2-->--3
 * @endverbatim
 * 现在来看看第7个单元格，我们看到它的顶部和底部的两条相对的线有不同的方向；因此，我们将发现没有任何方向的第7个单元格可以在不违反三角形的一致性的情况下被添加。根据上述规则，我们回到索引最大的邻居，也就是单元格6，但由于它的底线是向右的，它的顶线也一定是向右的，所以我们无法找到单元格6的方向，从而使7符合三角形。然后，如果我们已经完成了单元格6的所有可能的方向，我们再追踪到6的最大索引的邻居，并且已经被添加了。然而，我们知道0号单元格的方向不可能是重要的，所以我们得出结论，没有任何可能的方法来确定给定单元格的所有线条的方向，使它们满足deal.II三角形的要求。我们知道这是不可能的，所以会导致抛出一个异常。
 * 这个例子的底线是，当我们看了所有可能的单元格6的方向时，我们找不到一个可以添加单元格7的方向，然后决定追踪回单元格0，我们甚至没有尝试转动单元格5，之后添加单元格7就很简单了。因此，必须修改上述算法：如果我们未能在任何方向上添加一个单元格，我们只允许追踪回已经添加的那个邻居，其单元格索引最大。如果我们进一步追踪，因为我们已经用尽了所有可能的方向，但可以添加细胞（即我们追踪，因为另一个细胞，更远的地方不能添加，不管我们现在考虑的细胞的方向），那么我们不允许追踪到它的一个邻居，但必须只追踪一个细胞指数。
 * 第二种修剪树的方法是，通常我们不能添加一个新的单元，因为它的一个已经被添加的邻居的方向是错误的。因此，如果我们可以尝试旋转其中一个邻居（当然要确保旋转该邻居不违反三角形的一致性），以允许现在的单元被添加。
 * 第一种方法可以解释为在方向树上一次回溯不止一步，而转动一个邻居则意味着跳到树上一个完全不同的地方。对于这两种方法，人们可以找到论据，认为它们永远不会错过有效的路径，反正只跳过无效的路径。
 * 这两种方法已经被证明是非常有效的。我们已经能够读取非常大的网格（几万个单元）而不需要回溯很多。特别是，我们发现找到单元格排序的时间与单元格的数量呈线性关系，而且重新排序的时间通常比从文件中读取数据所需的时间小得多（例如一个数量级），同时也比使用
 * Triangulation::create_triangulation()
 * 函数从这些数据中实际生成三角图所需的时间小。
 *
 * @ingroup grid
 *
 */


